package algocasts;

import java.util.HashMap;
import java.util.Map;

public class P102_CopyListWithRandomPointer {
    class Node {
        int val;
        Node next, random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    // Time: O(n)  Space: O(n)
    public Node copyRandomList_HashMap(Node head) {
        if (head == null) return null;
        Map<Node, Node> map = new HashMap<>();
        Node copyHead = new Node(head.val);
        map.put(head, copyHead);
        for (Node p = head.next, q = copyHead; p != null; p = p.next, q = q.next) {
            q.next = new Node(p.val);
            map.put(p, q.next);
        }
        for (Node p = head, q = copyHead; p != null; p = p.next, q = q.next) {
            if (p.random != null) {
                q.random = map.get(p.random);
            }
        }
        return copyHead;
    }

    // Time: O(n)  Space: O(1)
    public Node copyRandomList_(Node head) {
        if (head == null) return null;
        for (Node p = head; p != null; p = p.next.next) {
            Node copy = new Node(p.val);
            copy.next = p.next;
            p.next = copy;
        }
        for (Node p = head; p != null; p = p.next.next)
            if (p.random != null)
                p.next.random = p.random.next;

        Node vnode = new Node(0);
        Node p = head, cp = vnode;
        while (p != null) {
            Node copy = p.next, next = p.next.next;
            cp.next = copy;
            cp = copy;
            p.next = next;
            p = next;
        }
        return vnode.next;
    }

}
